import java.util.PriorityQueue;

public class 二分谷歌面试 {
    // 计算等位时间
    // 给定一个数组arr长度为n，表示n个服务员，每服务一个人的时间
    // 给定一个正数m，表示有m个人等位，如果你是刚来的人，请问你需要等多久？
    // 假设m远远大于n，比如n <= 10^3, m <= 10^9，该怎么做是最优解？
    // 谷歌的面试，这个题连考了2个月

    //方法一, 堆结构在数据量比较小的时候
    public static int waitingTime(int[] arr, int m){
        //构造小根堆
        PriorityQueue<int[]> heap = new PriorityQueue<>((x,y) ->{
            return x[0] - y[0];
        });
        //将每一个服务员的时间点和每次服务时间添加进去
        for (int i = 0; i < arr.length; i++) {
            heap.offer(new int[]{0,arr[i]});
        }
        //每次拿回再重新添加
        for (int i = 0; i < m; i++) {
            int[] t = heap.poll();
            heap.offer(new int[]{t[0] + t[1],t[1]});
        }
        //拿到的时候返回最短时间的值
        return heap.poll()[0];
    }


    //方法二, 二分, 可以在大数据时使用
    public static int waitingTime1(int[] arr, int m){
        int min = 0;
        //找出最小值, 确定二分的范围先
        for (int i = 0; i < arr.length; i++) {
            min = Math.max(arr[i],min);
        }
        long l = 0;
        long r = (long)min * m;
        long ret = 0;
        while (l <= r){
            long mid = (l + r) / 2;
            /*
            比较的是时间能服务几个人, 这里是m + 1 是因为我们找的是需要服务几个人, 所以前m个人服务完后自己也要有时间
             */
            if(f(arr,mid) >= m + 1){
                ret = mid;
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }
        return (int)ret;
    }

    private static long f(int[] arr, long mid) {
        int sum = 0;
        //每一个服务员能服务几个人
        for(int num : arr){
            /*
            比如服务一个人2分钟, 4分钟可以服务3个人,因为第四分钟一到就可以服务下一个人所以+1
            比如服务一个人2分钟, 3分钟可以服务2个人,其中一个人正在被服务中
             */
            sum += (mid / num) + 1;
        }
        return sum;
    }
    public static void main(String[] args) {
        System.out.println("测试开始");
        int N = 50;
        int V = 30;
        int M = 3000;
        int testTime = 20000;
        for (int i = 0; i < testTime; i++) {
            int n = (int) (Math.random() * N) + 1;
            int[] arr = randomArray(n, V);
            int m = (int) (Math.random() * M);
            int ans1 = waitingTime(arr, m);
            int ans2 = waitingTime1(arr, m);
            if (ans1 != ans2) {
                System.out.println("出错了!");
            }
        }
        System.out.println("测试结束");
    }

    // 对数器测试
    public static int[] randomArray(int n, int v) {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = (int) (Math.random() * v) + 1;
        }
        return arr;
    }
}
